#include <bits/stdc++.h>
using namespace std;

/*
3439. 重新安排会议得到最多空余时间 I
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。

同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为 [startTime[i], endTime[i]] 。

你可以重新安排 至多 k 个会议，安排的规则是将会议时间平移，且保持原来的 会议时长 ，你的目的是移动会议后 最大化 相邻两个会议之间的 最长 连续空余时间。

移动前后所有会议之间的 相对 顺序需要保持不变，而且会议时间也需要保持互不重叠。

请你返回重新安排会议以后，可以得到的 最大 空余时间。

注意，会议 不能 安排到整个活动的时间以外。

 

示例 1：

输入：eventTime = 5, k = 1, startTime = [1,3], endTime = [2,5]

输出：2

解释：



将 [1, 2] 的会议安排到 [2, 3] ，得到空余时间 [0, 2] 。

示例 2：

输入：eventTime = 10, k = 1, startTime = [0,2,9], endTime = [1,4,10]

输出：6

解释：



将 [2, 4] 的会议安排到 [1, 3] ，得到空余时间 [3, 9] 。

示例 3：

输入：eventTime = 5, k = 2, startTime = [0,1,2,3,4], endTime = [1,2,3,4,5]

输出：0

解释：

活动中的所有时间都被会议安排满了。

 

提示：

1 <= eventTime <= 109
n == startTime.length == endTime.length
2 <= n <= 105
1 <= k <= n
0 <= startTime[i] < endTime[i] <= eventTime
endTime[i] <= startTime[i + 1] 其中 i 在范围 [0, n - 2] 之间。
*/

// 法一
class Solution {
public:
    int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
        int n = startTime.size(), res = 0;  // n: 会议数量，res: 存储最大空余时间
        vector<int> sum(n + 1);             // 前缀和数组，sum[i]表示前i个会议的总持续时间
        
        // 计算前缀和：sum[i+1] = 前i个会议的累计时长
        for (int i = 0; i < n; i++) {
            sum[i + 1] = sum[i] + endTime[i] - startTime[i];  // 存储每个会议的持续时间累加值
        }
        
        // 滑动窗口遍历所有可能的连续k个会议组合
        for (int i = k - 1; i < n; i++) {
            // 计算当前窗口的右边界：
            // - 若是最后一个会议：右边界=活动结束时间
            // - 否则：右边界=下一个会议的开始时间
            int right = i == n - 1 ? eventTime : startTime[i + 1];  
            
            // 计算当前窗口的左边界：
            // - 若窗口从第一个会议开始：左边界=0（活动起始时间）
            // - 否则：左边界=窗口前一个会议的结束时间
            int left = i == k - 1 ? 0 : endTime[i - k];  
            
            // 计算当前窗口的空闲时间：
            // 总区间长度(right-left) 减去 窗口内k个会议的总时长
            int windowFreeTime = right - left - (sum[i + 1] - sum[i - k + 1]);  
            
            // 更新全局最大空余时间
            res = max(res, windowFreeTime);  
        }
        return res;  // 返回所有窗口中最大的空余时间
    }
};

// 法二
class Solution {
public:
    int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
        int n = startTime.size();
        // 创建空余时间前缀和数组（size=n+1）
        vector<int> spareTime(n + 1, 0);
        
        // 计算第一个会议开始前的空闲时间
        spareTime[0] = startTime[0];
        
        // 计算会议之间的空闲时间（前缀和）
        for(int i = 1; i < n; i++){
            // 当前空闲时间 = 当前会议开始 - 前一个会议结束 + 之前累计空闲时间
            spareTime[i] = startTime[i] - endTime[i - 1] + spareTime[i - 1];
        }
        
        // 计算最后一个会议结束到活动结束的总空闲时间
        spareTime[n] = eventTime - endTime[n - 1] + spareTime[n - 1];
        
        // 初始化答案为前k个会议的空闲时间总和
        int ans = spareTime[k];
        
        // 使用滑动窗口寻找最大空闲时间段
        for(int i = k + 1; i < n + 1; i++){
            // 计算长度为k+1的窗口内空闲时间和（当前窗口和 - 前一个窗口起始点）
            ans = max(ans, spareTime[i] - spareTime[i - k - 1]);
        }
        
        return ans;
    }
};